The present invention relates generally to error correcting codes implemented in computer memory systems.
During the process of storing data in computer memory and then retrieving it, the data may be corrupted; therefore an error-correcting-code is used to encode the data before it is stored, and decode it after it was retrieved. Very often a Reed-Solomon (RS) code is used. The overall RS encode and decode process is shown in respective FIGS. 1A and 1B which, in sum, depicts an error correction system, implementing, for example, a Reed Solomon encoding scheme. Generally, in the encode system 10 shown in FIG. 1A, during a write operation, the raw data 12, usually a cache line, is input to an encoder device 15 which computes and adds check symbols 20 to the data and stores a code-word 25 (data including the check symbols) in a memory storage device.
In some instances, during transmission to a memory storage device, the encoded word may become corrupted and contain errors. In the decode system 30 shown in FIG. 1B, the code-word 25′ which may contain errors is read from memory during a read operation, and the code-word is sent to an (error correcting circuit) ECC, e.g., including an RS-Decoder 50 and a syndrome generator which corrects any errors which had occurred, and stores the encoded data 55 is forwarded to the cache, for example.
The first stage of the Decoder of a Reed-Solomon code is the Syndrome-generator 40 for calculating syndromes that will be key in detecting where the errors are and correcting the errors. In some serial implementations, syndrome calculation may take one clock cycle for each syndrome calculation, which speed may suffice for hard disk drives, but would exhibit undue amount of latency for error correcting codes used for computer memory (RAM, SRAM, etc.).
Since latency is critical, the usual parallel implementation of both the Syndrome-generator and the Encoder requires a large amount of circuitry when Reed-Solomon codes are used to protect the data in memory, such as computer memory since both of these modules have a large number of inputs: the Syndrome-generator 40, for example, receives and uses all the data read from memory to generate the syndromes, and the Encoder 15 receives and uses all the data to be stored in memory to generate the check symbols.
Ideally, the entire RS decoder circuitry for computer circuitry needs to complete in a very small number of cycles, and it would be highly desirable to provide a circuit implementation that encodes all the data or computes syndromes in parallel in a minimum of clock cycles, e.g., one or 2 clock cycles.
It would be highly desirable to provide a parallel-implemented ECC system of reduced circuit size and method for computing check symbols and syndromes for error correcting codes in a computer memory system.